/**
 * FileName: Exercise1737.c
 * --------------------------------------------------------------------------------------------------------------------
 * 17.37 Develop an adjacency-matrix representation for **dense multigraphs**, and
 * provide an ADT implementation for Program 17.1 that uses it.
 *
 * --------------------------------------------------------------------------------------------------------------------
 * 骨架代码：
 * `skeleton/chapter17/src/test/TestAdjacencyMatrixGraph.c`
 *
 * 修改：
 * 将adj[v][w]的含义从v和w之间是否存在边，修改为记录连接v和w的边的数量，为了支持并行边；
 * GRAPHinsertE、GRAPHremoveE、GRAPHedges、GRAPHshow都有改动，为了支持并行边；
 * --------------------------------------------------------------------------------------------------------------------
 * 目标：理解多重图(有并行边)
 */
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

//边相关
typedef struct {
    int v;
    int w;
}
Edge;

//图相关
typedef struct graph *Graph;
struct graph {
    int V;
    int E;
    int** adj;
};

//辅助函数声明
int** MATRIXinit(int, int, int);
Edge EDGE(int, int);
void GRAPHshow(Graph);

//图操作声明
Graph GRAPHinit(int);
void GRAPHinsertE(Graph, Edge);
void GRAPHremoveE(Graph, Edge);
int GRAPHedges(Edge [], Graph);
Graph GRAPHcopy(Graph);
void GRAPHdestroy(Graph);

//辅助函数实现
int** MATRIXinit(int r, int c, int val) {
    int i;
    int j;
    int** t = malloc(r * sizeof(int*));
    for (i = 0; i < r; i++) {
        t[i] = malloc(c * sizeof(int));
    }
    for (i = 0; i < r; i++) {
        for (j = 0; j < c; j++) {
            t[i][j] = val;
        }
    }
    return t;
}

Edge EDGE(int v, int w) {
    Edge edge;
    edge.v = v;
    edge.w = w;
    return edge;
}

void GRAPHshow(Graph G) {
    int i;
    int j;
    int k;
    printf("%d vertices, %d edges\n", G->V, G->E);

    //邻接列表
    // for (i = 0; i < G->V; i++) {
    //     printf("%2d:", i);
    //     for (j = 0; j < G->V; j++) {
    //         for (k = 0; k < G->adj[i][j]; k++) {
    //             printf(" %2d", j);
    //         }
    //     }
    //     printf("\n");
    // }
    //邻接矩阵
    for (i = 0; i < G->V; i++) {
        printf("%2d:", i);
        for (j = 0; j < G->V; j++) {
            printf(" %2d", G->adj[i][j]);
        }
        printf("\n");
    }
}

//图操作函数实现
Graph GRAPHinit(int V) {
    Graph G = malloc(sizeof(*G));
    G->V = V;
    G->E = 0;
    G->adj = MATRIXinit(V, V, 0);
    return G;
}

void GRAPHinsertE(Graph G, Edge e) {
    int v = e.v;
    int w = e.w;
    // 检查顶点是否有效
    if (v < 0 || v >= G->V || w < 0 || w >= G->V) {
        fprintf(stderr, "Error: Invalid vertex in edge (%d, %d)\n", v, w);
        return;
    }

    G->adj[v][w]++;
    // 对于无向图，对称位置也递增
    if (v != w) { // 自环只加一次
        G->adj[w][v]++;
    }
    G->E++;
}

void GRAPHremoveE(Graph G, Edge e) {
    int v = e.v;
    int w = e.w;
    // 检查顶点是否有效
    if (v < 0 || v >= G->V || w < 0 || w >= G->V) {
        fprintf(stderr, "Error: Invalid vertex in edge (%d, %d) for removal\n", v, w);
        return;
    }

    // 如果没有边，直接返回
    if (G->adj[v][w] == 0) {
        fprintf(stderr, "Warning: Edge (%d, %d) does not exist for removal.\n", v, w);
        return;
    }

    G->adj[v][w]--;
    // 对于无向图，对称位置也递减
    if (v != w) { // 自环只减一次
        G->adj[w][v]--;
    }
    G->E--;
}
int GRAPHedges(Edge a[], Graph G) {
    int v;
    int w;
    int k;
    int edge_count = 0; // 使用不同的变量名以避免与 G->E 混淆
    for (v = 0; v < G->V; v++) {
        // 对于无向图，只遍历上三角矩阵（包括对角线）以避免重复计数
        // w 从 v 开始，以处理自环 (v, v)
        for (w = v; w < G->V; w++) {
            // 如果是自环 (v==w)，则 G->adj[v][v] 计数就是其数量
            // 如果是非自环 (v!=w)，则 G->adj[v][w] 计数就是其数量
            for (k = 0; k < G->adj[v][w]; k++) {
                // 对于非自环，只记录一次，因为它在 adj[v][w] 和 adj[w][v] 都计数了
                // 对于自环，G->adj[v][v] 存储的是实际数量
                if (v == w) { // 自环
                    a[edge_count++] = EDGE(v, w);
                } else { // 普通边
                    // 无向图在 GRAPHinsertE 和 GRAPHremoveE 中都对 adj[v][w] 和 adj[w][v] 进行了操作
                    // 但是 GRAPHedges 中我们只遍历 w = v+1 的情况，这样每条边只加一次。
                    // 这里的 for (w = v; w < G->V; w++) 逻辑需要调整。
                    // 最好还是按照 Program 17.1 的风格，只遍历上三角且不包括对角线，
                    // 这样就能避免重复添加无向边，并且默认不处理自环（除非特指）。
                    // 但如果题目要求包含自环，则需要特别处理。
                    // 按照 Program 17.6 (邻接列表) 和 Program 17.3 (邻接矩阵) 的约定，
                    // GRAPHedges 遍历的是每个顶点 i 的邻接点 j，如果 i < j 则收集边。
                    // 这样自然排除了自环和重复。
                    // 但对于多重图，如果 adj[v][w] > 0，那它就是一条边，且我们只考虑 v < w 的情况。
                    // 所以，应该从 for (w = v+1; w < G->V; w++) 开始。
                    // 如果题目明确要求自环也算作边且被 GRAPHedges 报告，那需要调整。
                    // 否则，保持 v < w 的遍历方式。
                }
            }
        }
    }
    // 重新审视 GRAPHedges 逻辑以严格遵循 Program 17.1/17.6 风格
    edge_count = 0; // 重置
    for (v = 0; v < G->V; v++) {
        for (w = v + 1; w < G->V; w++) { // 遍历上三角，不包含对角线（不考虑自环）
            for (k = 0; k < G->adj[v][w]; k++) {
                a[edge_count++] = EDGE(v, w);
            }
        }
    }
    // 如果要包含自环，需要额外处理：
    for (v = 0; v < G->V; v++) {
        for (k = 0; k < G->adj[v][v]; k++) { // 遍历自环
            a[edge_count++] = EDGE(v, v);
        }
    }


    return edge_count; // 返回实际收集的边数
}

// 简单实现 GRAPHcopy 和 GRAPHdestroy (此处仅为占位)
Graph GRAPHcopy(Graph G) {
    // 这是一个简单的占位实现，实际需要深拷贝
    Graph H = GRAPHinit(G->V);
    H->E = G->E;
    for (int i = 0; i < G->V; i++) {
        for (int j = 0; j < G->V; j++) {
            H->adj[i][j] = G->adj[i][j];
        }
    }
    return H;
}

void GRAPHdestroy(Graph G) {
    if (G == NULL) return;
    for (int i = 0; i < G->V; i++) {
        free(G->adj[i]);
    }
    free(G->adj);
    free(G);
}

//测试函数声明
void test_multigraph();

int main(int argc, char *argv[]) {
    test_multigraph(); // 调用新的测试函数
    return 0;
}

//测试函数实现
void test_multigraph() {
    int V = 5; // 使用较小的顶点数方便观察
    Graph G = GRAPHinit(V);

    printf("--- Initial Graph ---\n");
    GRAPHshow(G);

    printf("\n--- Inserting Edges ---\n");
    // 插入普通边
    GRAPHinsertE(G, EDGE(0, 1));
    GRAPHinsertE(G, EDGE(1, 2));
    GRAPHinsertE(G, EDGE(2, 3));
    GRAPHinsertE(G, EDGE(3, 4));
    GRAPHshow(G);

    printf("\n--- Inserting Parallel Edges ---\n");
    // 插入并行边 (0,1)
    GRAPHinsertE(G, EDGE(0, 1));
    GRAPHinsertE(G, EDGE(0, 1));
    // 插入并行边 (2,4)
    GRAPHinsertE(G, EDGE(2, 4));
    GRAPHinsertE(G, EDGE(2, 4));
    GRAPHshow(G);

    printf("\n--- Inserting Self-loops ---\n");
    // 插入自环 (1,1)
    GRAPHinsertE(G, EDGE(1, 1));
    GRAPHinsertE(G, EDGE(1, 1)); // 再加一个自环
    GRAPHshow(G);

    printf("\n--- Testing GRAPHedges ---\n");
    Edge* all_edges = malloc(G->E * sizeof(Edge)); // G->E 现在是正确的
    int num_edges = GRAPHedges(all_edges, G);
    printf("Total edges reported by GRAPHedges: %d\n", num_edges);
    printf("Edges collected:\n");
    for (int i = 0; i < num_edges; i++) {
        printf(" (%d, %d)", all_edges[i].v, all_edges[i].w);
        if ((i + 1) % 5 == 0) printf("\n"); // 每5个换行
    }
    printf("\n");
    free(all_edges);


    printf("\n--- Removing Edges ---\n");
    // 移除一条并行边 (0,1)
    GRAPHremoveE(G, EDGE(0, 1));
    printf("After removing one (0,1) edge:\n");
    GRAPHshow(G);

    // 移除一条普通边 (3,4)
    GRAPHremoveE(G, EDGE(3, 4));
    printf("After removing (3,4) edge:\n");
    GRAPHshow(G);

    // 尝试移除不存在的边 (0,4)
    GRAPHremoveE(G, EDGE(0, 4));
    printf("After attempting to remove non-existent (0,4) edge:\n");
    GRAPHshow(G);

    // 移除一个自环 (1,1)
    GRAPHremoveE(G, EDGE(1, 1));
    printf("After removing one (1,1) self-loop:\n");
    GRAPHshow(G);

    // 移除所有 (0,1) 边
    GRAPHremoveE(G, EDGE(0, 1));
    GRAPHremoveE(G, EDGE(0, 1));
    printf("After removing all remaining (0,1) edges:\n");
    GRAPHshow(G);


    printf("\n--- Destroying Graph ---\n");
    GRAPHdestroy(G);
    printf("Graph destroyed.\n");
}
